package com.youth.day01;

/**
 * 插入排序
 * @author Jinx
 * @date 2021/6/12 23:37
 */
public class InsertSort {


    /**
     *  时间复杂度：O(n²)
     */
    public static int[] sort(int[] arr){
        if(arr == null || arr.length < 1){
            return arr;
        }

        // 前后两个指针  如果后者大，两个一起右移，如果小遍历和前面所有比较插入
        int temp;
        for (int i = 1; i < arr.length; i++) {
            if(arr[i] < arr[i-1]){
                temp = arr[i];
                arr[i] = arr[i-1];
                for (int j = i-1; j >= 0; j--) {
                    if(j-1 >= 0){
                        if(temp >= arr[j-1]){
                            arr[j] = temp;
                            break;
                        }
                        arr[j] = arr[j-1];
                    }else {
                        arr[j] = temp;
                    }
                }
            }
        }

        return arr;
    }
}
